#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct SNode *PtrToSNode;
struct SNode {
    int Data;
    PtrToSNode Next;
};
typedef PtrToSNode Stack;

Stack CreateStack();

bool IsEmpty( Stack S );

bool Push ( Stack S, int X );

int Pop ( Stack S );

int main() {
    Stack S = CreateStack();
    int choice, X, result, i = 1;

    while(1) {
        printf("Stack\r\nPlease input\r\n1 Push\t2 Pop\n3 Print\t4 Exit\n");
        scanf("%d",&choice);
        switch (choice) {
        case 1:
            printf("Please input\n");
            scanf("%d",&X);
            if ( Push(S,X) ) printf("Success Push\n");
            break;
        case 2:
            if ( IsEmpty(S) ) {
                printf("Empty\n");
                exit(-9);
            }
            result = Pop(S);
            printf("Pop\t%d\n",result);
            break;
        case 3:
            printf("data\n");
            Stack p = S;
            while(p) {
                printf("%d\t|\t%d\n",i++,p->Data);
                p = p->Next;
            }
            break;
        case 4:
            i = 0;
            while (S) {
                Pop(S);
                printf("Free success!\ncnt = %d\n",++i);
            }
            free(S);            
            
            exit(0);
            break;
        }
    }
    return 0;
}

Stack CreateStack() {
    Stack S;

    S = (Stack)malloc(sizeof(struct SNode));
    S->Next = NULL;
    return S;
}

bool IsEmpty( Stack S ) {
    return (S->Next == NULL);
}

bool Push ( Stack S, int X ) {
    PtrToSNode TmpCell;

    TmpCell = (PtrToSNode)malloc(sizeof(struct SNode));
    TmpCell->Data = X;
    TmpCell->Next = S->Next;
    S->Next = TmpCell;
    return true;
}

int Pop ( Stack S ) {
    PtrToSNode FirstCell;
    int TopElem;

    if(IsEmpty(S)) {
        printf("Empty\n");
        exit(-9);
    }
    FirstCell = S->Next;
    TopElem = FirstCell->Data;
    S->Next = FirstCell->Next;
    free(FirstCell);
    return TopElem;
}